package datastructure.sort;

import utils.Utils;

import java.util.Arrays;

import static datastructure.sort.MergeSort.mergeSort;
import static utils.Utils.shuffle;
import static utils.Utils.swap;


/**
 * @Author ZhangCuirong
 * @Date 2025/7/30 9:24
 * @description: 堆排序
 */
public class HeapSort {
    public static void heapSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        //从最后一个非叶子结点向上调整堆
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            adjustHeap(nums, i, nums.length);
        }
        int heapSize = nums.length;
        while (heapSize > 1) {
            //将根结点和堆的最后一个结点交换
            swap(nums, 0, heapSize - 1);
            //减少堆大小
            heapSize--;
            //调整堆
            adjustHeap(nums, 0, heapSize);
        }
    }
    /**
     * 向下调整堆的过程
     *
     * @param nums
     * @param index
     * @param heapSize
     */

    public static void adjustHeap(int[] nums, int index, int heapSize) {
        //左右结点
        int l = index * 2 + 1;
        int r = index * 2 + 2;
        int largest = index;
        //找到最大的元素
        if (l < heapSize && nums[l] > nums[largest]) {
            largest = l;
        }
        if (r < heapSize && nums[r] > nums[largest]) {
            largest = r;
        }
        if (index != largest) {
            //交换最大元素
            swap(nums, largest, index);
            //交换元素的位置调整堆
            adjustHeap(nums, largest, heapSize);
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 4, 6, -1, -4, -10};
        shuffle(nums);
        System.out.println(Arrays.toString(nums));
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
